#include <stdio.h>

int main(int argc, const char** args) {
	int arr[] = {2, 1, 5, 3, 6, 4, 8, 9, 7};
	int n = sizeof(arr) / sizeof(int);
	int dp[n];  // dp[i]为到arr[i]为止递增最长子序列长度
				// dp[i] = max(dp[i], dp[j] + 1]) if arr[i]>arr[j] 要与前面的所有元素比较
				// init: dp[i] = 1
	int i, j;
	int max = 0;
	for (i = 0; i < n; ++i) {
		dp[i] = 1;
	}

	for (i = 1; i < n; ++i) {
		for (j = 0; j < i; ++j) {		
			if (arr[i] > arr[j]) {
				dp[i] = dp[i] > (dp[j]+1) ? dp[i] : (dp[j]+1);
			}
		}
	}

	for (i = 1; i < n; ++i) {
		max = dp[i] > dp[i-1] ? dp[i] : dp[i-1];
	}

	printf("arr[]: ");
	for (i = 0; i < n; ++i) {
		printf("%d ", arr[i]);
	}
	printf("\nresult: %d\n", max);

	return 0;
}

